package org.java.test;

import java.util.Comparator;

/**
 * 递归方式实现二叉排序树,采用二叉链表的存储方式
 */
public class BinarySortTree<T> implements Comparator<T>{
	private Node<T> root;
	//静态内部类，跟外部类存在寄生关系，此时外部类相当于一个包，实现了更深层次的封装
	private static class Node<T> {
		private Node<T> left;
		private Node<T> right;
		private T data;
		private Node(T newData){
			this.left = null ; 
			this.right=null;
			this.data=newData;
		}
	}
	/**
	 * 创建一棵空的二叉树
	 */
	public BinarySortTree(){
		root=null;
	}
	/**
	 * 插入一个新节点
	 * @param data
	 */
	private void insert(T data) {
	    root = insert(root,data);
	}
	/**
	 * 递归查找合适位置，并插入
	 * @param node
	 * @param data
	 * @return
	 */
	private Node<T> insert(Node<T> node,T data){
		if(node==null){
			node=new Node<T>(data);
			//System.out.println(root.data);
		}else{
			if(compare((T)node.data,data)>0){
				node.left=insert(node.left,data);
			}else { 
		        node.right = insert(node.right ,data); 
		    } 
		}
		return node;
	}
	/**
	 * 将数组元素构建为一棵二叉排序树 
	 */
	public void buildTree(T[] data){ 
		for(int i=0;i<data.length;i++){
			insert(data[i]);
		}
	} 
	/**
	 * 从根节点迭代二叉树
	 */
	public void printTree() { 
	     iteratorTree(root); 
	} 
	/**
	 * 中序遍历二叉排序树
	 */
	private void iteratorTree(Node<T> node) { 
	     if (node == null ){
	    	 return ; 
	     }
	     // 中序遍历：left, node itself, right 
	     iteratorTree(node.left); 
	     System.out.print(node.data + "\t" ); 
	     iteratorTree(node.right); 
    }
	/**
	 * Comparator比较器的一个比较规则
	 */
	public int compare(T o1, T o2) {
		if(o1.getClass()==Integer.class){
			Integer obj1=(Integer)o1;
			Integer obj2=(Integer)o2;
			if(obj1>=obj2){
				return 1;
			}else{
				return -1;
			}
		}
		// TODO Auto-generated method stub
		return 0;
	}
	
	//==================================================================	
	/**
	 * 以下为测试代码
	 */
	public static void main(String[] args) {
		BinarySortTree<Integer> biTree=new BinarySortTree<Integer>(); 
        Integer[] data=new Integer[]{5,6,2,8,7,4,1,3}; 
        biTree.buildTree(data); 
        biTree.printTree(); 
	}
}
